vector<FeatureDescriptor * > * kmeans(vector<FeatureDescriptor *> input, int nr_restarts, int iterations, int nr_clusters)
{
	printf("doing kmeans with %i features\n",input.size());
	float best_sum = -1;
	vector<FeatureDescriptor * > * best_centers = new vector<FeatureDescriptor * >();
	for(int restart = 0; restart < nr_restarts; restart++)
	{
		printf("--------------------------------------------------------------------------------\n");
		vector<FeatureDescriptor * > * centers = new vector<FeatureDescriptor * >();
		for(int j = 0; j < nr_clusters; j++){centers->push_back(input.at(rand()%input.size())->clone());}
		float sum;
		
		for(int iter = 0; iter < iterations; iter++)
		{
			vector< vector<FeatureDescriptor * > * > * centers_data = new vector< vector <FeatureDescriptor * > * >();
			for(int j = 0; j < nr_clusters; j++){centers_data->push_back(new vector<FeatureDescriptor *>());}
			
			sum = 0;
			for(int i = 0; i < input.size(); i++)
			{
				FeatureDescriptor * current = input.at(i);
				float best = 99999;
				int best_id = -1;
				for(int j = 0; j < nr_clusters; j++)
				{
					float dist = current->distance(centers->at(j));
					
					if(best > dist){
						best = dist;
						best_id = j;
					}
				}
				sum+=best*best;
				centers_data->at(best_id)->push_back(current);
			}
			
			sum /= float(input.size());
			printf("errorsum: %f\n",sum);
			/*
			for(int j = 0; j < nr_clusters; j++)
			{
				if(centers_data[j].size() > 0){
					delete centers[j];
					centers[j] = new FeatureDescriptor(centers_data[j]);
				}
			}
			*/
			for(int j = 0; j < nr_clusters; j++){delete centers_data->back(); centers_data->pop_back();}
			delete centers_data;
		}
		/*
		if(best_sum == -1){
			best_centers = centers;
			best_sum = sum;
		}else if(sum < best_sum){
			for(int i = 0; i < nr_clusters; i++){delete centers[i];}
			delete[] centers;
			best_centers = centers;
			best_sum = sum;
		}else{
			for(int i = 0; i < nr_clusters; i++){delete centers[i];}
			delete[] centers;
		}
		*/
	}
	return best_centers;
}
